package org.example.myleet.greedy;

import org.example.myleet.Utils.Assert;

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

public class GreedySolution {

    /**
     * 134【贪心】加油站
     * 取巧办法，来自"陈允怀"
     * 0 ms
     * 复杂度O(n)，n为加油站个数
     */
    public int canCompleteCircuit(int[] gas, int[] cost) {
        //start表示从哪个加油站出发，0下标开始
        //run表示当前前往下一个加油站这个过程完成之后的剩余油量
        //delta表示加油站加完油之后去下一个加油站这个过程的油量差值，减少一次加法计算而已
        //rest表示整个行进过程的油量剩余值，小于0时表示旅途不可完成
        int start = 0, delta = 0, run = 0, rest = 0;
        for (int i=0; i<gas.length; i++) {
            //逐个加油站遍历
            //计算这个加油站加完油之后去下一个加油站这个过程的油量差值，可能有剩余，可能有亏空
            delta = gas[i] - cost[i];
            //上一个状态叠加本趟去往下一个加油站的油耗
            run = run + delta;
            if (run < 0) {
                //叠加完状态发现其实这样是跑不到下一个加油站的，于是从下一个加油站开始推演新的过程
                //因为是从第0个加油站开始推演的，因此只要run在第m个站不行，说明前m个站都不能作为起始点
                run = 0;
                start = i+1;
            }
            //整个行进过程的油量剩余值累加，累计剩余油量和亏空油量
            rest += delta;
        }
        if (rest < 0) {
            return -1;
        }
        return start;
    }

    /**
     * 334【贪心】递增的三元子序列
     */
    public boolean increasingTriplet(int[] nums) {
        if (nums.length < 3) {
            return false;
        }
        //贪心思路，min1保持最小，min2保持比min1大的最小（次小值），且min2的特性是三元递增组合中的第2个，所以只要存在nums[i] > min2，则有解
        int min1, min2;
        if (nums[0] < nums[1]) {
            min1 = nums[0];
            min2 = nums[1];
        } else {
            min1 = nums[1];
            //未找到min2，先凑合着
            min2 = Integer.MAX_VALUE;
        }
        int n = nums.length;
        for (int i = 2; i < n; ++i) {
            if (min2 < nums[i]) {
                //存在nums[i] > min2，有解
                return true;
            }
            //下面对min1和min2更新
            if (min1 > nums[i]) {
                //找到比min1更小，更新最小值
                min1 = nums[i];
            } else if (min1 != nums[i] && min2 > nums[i]) {
                //注意min1 == nums[i]时不能更新min2，因为min2不能等于min1，因此当min2 > nums[i]时，nums[i]即为当前扫描发现得到的次小值
                min2 = nums[i];
            }
        }
        return false;
    }

    //p670
    public int maximumSwap(int num) {
        if (num < 10) {
            return num;
        }
        //贪心：
        //1、先定位排前头的数字哪一位需要被替换，需要满足条件是这位数字不是从这位开始的数字后缀中最大的数字
        //例如98368，第3位的"3"这位才满足需要被交换，"10909091"则第1位就可以被交换
        //2、找到需要被交换的位置后，找到后缀中最后一位最大的数字，与需要交换位置进行交换得到最大数字
        char[] number = Integer.toString(num).toCharArray();
        int n = number.length, swapIdx = 0;
        //一次遍历找到num的每一个后缀中最大的单个数字
        char[] suffixMaxChar = new char[n];
        char maxChar = 0;
        for (int i = n - 1; i >= 0; --i) {
            maxChar = (char) Math.max(maxChar, number[i]);
            suffixMaxChar[i] = maxChar;
        }
        while (swapIdx < n) {
            //逐位寻找是否存在可以交换位置swapIdx
            if (number[swapIdx] == suffixMaxChar[swapIdx]) {
                //如果swapIdx就是后缀中最大的数字，则不能作为交换位置
                ++swapIdx;
                continue;
            }
            //找到swapIdx座位交换位置，然后从后缀的结尾开始往前扫描找到最末端的最大数字，交换完成
            for (int i = n - 1; i > swapIdx; --i) {
                if (number[i] == suffixMaxChar[swapIdx]) {
                    char t = number[i];
                    number[i] = number[swapIdx];
                    number[swapIdx] = t;
                    break;
                }
            }
            break;
        }
        return Integer.parseInt(new String(number));
    }

    /**
     * 670.【贪心】最大交换
     */
    public int maximumSwap1(int num) {
        String numStr = Integer.toString(num);
        char[] dCharArr = numStr.toCharArray();
        for (int i = 0; i < numStr.length(); ++i) {
            char ci = dCharArr[i];
            //贪心：找到任意j > i，且第j位数字满足num[j] > num[i]，且num[j]是所有位中数字最大的，且这个j要尽量大
            //满足以上条件的j就是跟第i位最佳的的交换位置j
            //如果没找到，就++i，继续重复这个程序找，如果遍历整个数都没找到就说明本身num已经是最大
            int mxj = i;
            for (int j = i + 1; j < numStr.length(); ++j) {
                if (ci < dCharArr[j] && dCharArr[mxj] <= dCharArr[j]) {
                    mxj = j;
                }
            }
            if (i != mxj) {
                char t = dCharArr[mxj];
                dCharArr[mxj] = dCharArr[i];
                dCharArr[i] = t;
                return Integer.parseInt(new String(dCharArr));
            }
        }
        return num;
    }

    /**
     * 765【贪心】情侣牵手
     * 0 ms
     * 贪心暴力循环法，如果每次交换都能配好一对而不破坏已经存在的配对，那么这次交换一定是至少要做的交换
     */
    public int minSwapsCouples(int[] row) {
        int count = 0;
        int n = row.length;
        outer:
        for (int i = 0; i < n; i++) {
            //每次从数组里面取2个数看看是不是配对的
            int one = row[i];
            int two = row[i + 1];
            int target;
            if ((one & 1) == 1) {
                target = one - 1;
            } else {
                target = one + 1;
            }
            if (two == target) {
                //已经是配对，则无需处理
                i++;
                continue;
            }
            //如果不是配对的，就找到配对的那个位置，并把这个不配对的值交换，完成一次有效交换
            for (int j = i + 2; j < n; j++) {
                if (row[j] == target) {
                    row[j] = two;
                    row[i + 1] = target;
                    ++count;
                    i++;
                    continue outer;
                }
            }
        }
        return count;
    }

    //p857
    /**
     * 贪心分析，假设选择了k个人，总工资为totalWage，每个人应得工资为 totalWage * (quality[x] / totalQuality) = wx，题意要求每个人应得工资不能低于w[i]
     * 得到不等式 totalWage * (quality[i] / totalQuality) >= w[i]
     * 转换不等式可知总工资的关系 totalWage >= (w[i] / quality[i]) * totalQuality，也就是 (w[i] / quality[i]) * totalQuality 的最大值要最小
     * 贪心：totalQuality可以通过维护一个优先堆保持尽量小，w[i] / quality[i] 可以通过排序保持尽量小
     */
    public double mincostToHireWorkers(int[] quality, int[] wage, int k) {
        int n = quality.length;
        double[] weights = new double[n];
        for (int i = 0; i < n; ++i) {
            weights[i] = (double) wage[i] / (double) quality[i];
        }
        Integer[] indexes = new Integer[n];
        for (int i = 0; i < n; ++i) {
            indexes[i] = i;
        }
        Arrays.sort(indexes, (o1, o2) -> {
            if (weights[o1] < weights[o2]) {
                return -1;
            } else if ((weights[o2] < weights[o1])) {
                return 1;
            }
            return 0;
        });
        int totalQuality = 0;
        double minRes = Double.MAX_VALUE;
        PriorityQueue<Integer> pq = new PriorityQueue<>(Comparator.reverseOrder());
        int i = 0;
        for (; i < k - 1; ++i) {
            pq.offer(quality[indexes[i]]);
            totalQuality += quality[indexes[i]];
        }
        for (; i < n; ++i) {
            int idx = indexes[i];
            totalQuality += quality[idx];
            pq.offer(quality[idx]);
            minRes = Math.min(minRes, weights[idx] * totalQuality);
            totalQuality -= pq.poll();
        }
        return minRes;
    }

    //p921
    public int minAddToMakeValid(String s) {
        char[] stack = new char[s.length()];
        int i = 0;
        for (char c : s.toCharArray()) {
            if (c == '(') {
                stack[i++] = c;
            } else if (c == ')') {
                if (i > 0 && stack[i - 1] == '(') {
                    --i;
                } else {
                    stack[i++] = c;
                }
            }
        }
        return i;
    }

    //1144
    public int movesToMakeZigzag(int[] nums) {
        //复制一次数组，用于奇数作为突出状情况的判断
        int n = nums.length;
        int[] cp = new int[n];
        System.arraycopy(nums, 0, cp, 0, n);
        //如果使奇数下标成为突出状情况所需最少操作次数
        int oddOpt = 0;
        for (int i = 0; i < n; i += 2) {
            int l = i - 1;
            if (l >= 0) {
                if (cp[l] >= cp[i]) {
                    oddOpt += cp[l] - cp[i] + 1;
                }
            }
            int r = i + 1;
            if (r < n) {
                if (cp[i] <= cp[r]) {
                    oddOpt += cp[r] - cp[i] + 1;
                    //右边下标减小
                    cp[r] = cp[i] - 1;
                }
            }
        }
        //如果使偶数下标成为突出状情况所需最少操作次数
        int evenOpt = 0;
        for (int i = 1; i < n; i += 2) {
            int l = i - 1;
            if (l >= 0) {
                if (nums[l] >= nums[i]) {
                    evenOpt += nums[l] - nums[i] + 1;
                }
            }
            int r = i + 1;
            if (r < n) {
                if (nums[i] <= nums[r]) {
                    evenOpt += nums[r] - nums[i] + 1;
                    //右边下标减小
                    nums[r] = nums[i] - 1;
                }
            }
        }
        return Math.min(oddOpt, evenOpt);
    }

    //p1326
    public int minTaps(int n, int[] ranges) {
        int[] rMost = new int[ranges.length];
        for (int i = 0; i <= n; i++) {
            rMost[i] = i;
        }
        for (int i = 0; i <= n; ++i) {
            //利用每个位置i的range数据更新其左端点所能到达的最远右端
            int l = Math.max(0, i - ranges[i]);
            rMost[l] = Math.max(rMost[l], Math.min(n, i + ranges[i]));
        }
        //curR当前能达到的最右端点，nextR是下一个水龙头能浇到的最远右端点
        int answer = 0, curR = 0, nextR = 0;
        for (int i = 0; i < n; ++i) {
            //更新下一个水龙头可以到达的最远距离
            nextR = Math.max(nextR, rMost[i]);
            if (i == curR) {
                //i到达curR，到达当前水龙头最远的位置
                if (i == nextR) {
                    //i到达下一个水龙头的最远位置，但是依然没能找出可以到达的下一个水龙头
                    return -1;
                }
                //选取下一个最远可以到达的水龙头
                curR = nextR;
                ++answer;
            }
        }
        return answer;
    }

    //p1605
    public int[][] restoreMatrix(int[] rowSum, int[] colSum) {
        int[][] answer = new int[rowSum.length][colSum.length];
        for (int i = 0; i < rowSum.length; ++i) {
            for (int j = 0; j < colSum.length; ++j) {
                answer[i][j] = Math.min(rowSum[i], colSum[j]);
                rowSum[i] -= answer[i][j];
                colSum[j] -= answer[i][j];
            }
        }
        return answer;
    }

    //p1663
    public String getSmallestString(int n, int k) {
        char[] alphabets = new char[n];
        k -= n;
        int i = n - 1;
        while (k > 0) {
            if (k > 25) {
                alphabets[i] = 'z';
                k -= 25;
            } else {
                alphabets[i] = (char) ('a' + k);
                k -= k;
            }
            --i;
        }
        while (i > -1) {
            alphabets[i] = 'a';
            --i;
        }
        return new String(alphabets);
    }
//    public String getSmallestString(int n, int k) {
//        int zCount = (k - n) / 25;
//        int aCount = Math.max(0, n - zCount - 1);
//        int p = k - 26 * zCount - aCount;
//        StringBuilder alphabets = new StringBuilder(n);
//        for (int i = 0; i < aCount; ++i) {
//            alphabets.append('a');
//        }
//        if (p > 0) {
//            alphabets.append((char) ('a' + p - 1));
//        }
//        for (int i = 0; i < zCount; ++i) {
//            alphabets.append('z');
//        }
//        return alphabets.toString();
//    }

    //p1775
    public int p1775MinOperations(int[] nums1, int[] nums2) {
        int sum1 = 0;
        for (int num : nums1) {
            sum1 += num;
        }
        int sum2 = 0;
        for (int num : nums2) {
            sum2 += num;
        }
        if (sum1 > sum2) {
            return p1775MinOperations(nums2, sum2, nums1, sum1);
        } else if (sum1 < sum2) {
            return p1775MinOperations(nums1, sum1, nums2, sum2);
        } else {
            return 0;
        }
    }
    private int p1775MinOperations(int[] smaller, int smallerSum, int[] bigger, int biggerSum) {
        if (smaller.length * 6 < bigger.length) {
            return -1;
        }
        int operations = 0;
        PriorityQueue<Integer> heap1 = new PriorityQueue<>(Comparator.naturalOrder());
        for (int num : smaller) {
            heap1.offer(num);
        }
        PriorityQueue<Integer> heap2 = new PriorityQueue<>(Comparator.reverseOrder());
        for (int num : bigger) {
            heap2.offer(num);
        }
        while (smallerSum < biggerSum) {
            //计算较小堆堆顶和较大堆堆顶的数值对于缩小差距的贡献
            int distribution1 = 0;
            if (!heap1.isEmpty()) {
                distribution1 = 6 - heap1.peek();
            }
            int distribution2 = 0;
            if (!heap2.isEmpty()) {
                distribution2 = heap2.peek() - 1;
            }
            if (distribution1 > distribution2) {
                //较小堆的堆顶修改后贡献更大，增加一次操作较小堆修改数字
                smallerSum += distribution1;
                heap1.poll();
            } else {
                biggerSum -= distribution2;
                heap2.poll();
            }
            ++operations;
        }
        return operations;
    }

    //1791
    public int findCenter(int[][] edges) {
        int[] edge0 = edges[0];
        int[] edge1 = edges[1];
        if (edge0[0] == edge1[0] || edge0[0] == edge1[1]) {
            return edge0[0];
        }
        if (edge0[1] == edge1[0] || edge0[1] == edge1[1]) {
            return edge0[1];
        }
        return edge0[0];
    }

    //p1798
    public int getMaximumConsecutive(int[] coins) {
        Arrays.sort(coins);
        int x = 0;
        for (int i = 0; i < coins.length; ++i) {
            if (coins[i] <= x + 1) {
                //如果coins[i]不超过x+1，则x可以到达[x+1, x+coins[i]]的范围
                x += coins[i];
            }
        }
        //算上x=0
        return x + 1;
    }

    //p1833
    public int maxIceCream(int[] costs, int coins) {
        Arrays.sort(costs);
        int iceCreamCount = 0;
        for (int i = 0; i < costs.length; ++i) {
            if (coins >= costs[i]) {
                ++iceCreamCount;
                coins -= costs[i];
            } else {
                return iceCreamCount;
            }
        }
        return iceCreamCount;
    }

    //1846
    public int maximumElementAfterDecrementingAndRearranging(int[] arr) {
        Arrays.sort(arr);
        arr[0] = 1;
        for (int i = 1; i < arr.length; ++i) {
            if (arr[i] > arr[i - 1]) {
                arr[i] = arr[i - 1] + 1;
            }
        }
        return arr[arr.length - 1];
    }

    //p1877
    /**
     * 贪心
     * 思路：
     * 题目要求组合的数对尽量小，一个反证法的思考过程是，数组中肯定有一个最大的数，这个数跟其他数组合成数对时，只有取最小的数组对才能尽量小
     * 最大的数和最小的数组对后，剩下的问题范围缩小了，但是性质不变，依然可以这样推理
     * 因此使用排序就可以得到很适合这种组对的情况的排列
     */
    public int minPairSum(int[] nums) {
        Arrays.sort(nums);
        int l = 0, r = nums.length - 1, max = nums[l] + nums[r];
        while (l < r) {
            max = Math.max(max, nums[l] + nums[r]);
            ++l;
            --r;
        }
        return max;
    }

    //1785
    public int minElements(int[] nums, int limit, int goal) {
        long sum = 0;
        for (int num : nums) {
            sum += num;
        }
        long diff = goal - sum;
        if (diff == 0) {
            return 0;
        } else {
            diff = Math.abs(diff);
            if (diff % limit == 0) {
                return (int) (diff / limit);
            }
            return (int) (diff / limit + 1);
        }
    }

    //p2029
    public boolean stoneGameIX(int[] stones) {
        int[] count = new int[3];
        for (int stone : stones) {
            ++count[stone % 3];
        }
        int[] copy = new int[count.length];
        System.arraycopy(count, 0, copy, 0, count.length);
        if (copy[1] > 0 && play2029(copy, 1)) {
            return true;
        }
        copy = new int[count.length];
        System.arraycopy(count, 0, copy, 0, count.length);
        if (copy[2] > 0 && play2029(copy, 2)) {
            return true;
        }
        return false;
    }
    /**
     * 模拟游戏过程，无论是Alice还是Bob，当所取石头总价值的余数为1时，下一个玩家需要取1或0，余数变为2；下一个玩家必须取2或0，余数变为1
     * @param count 石头的余数是0、1、2的数量
     * @param start Alice从余数为1还是2的石头开始取
     * @return Alice是否能够赢
     */
    private boolean play2029(int[] count, int start) {
        //初始化，Alice取完，轮到Bob取
        boolean alice = false;
        int remainder = start;
        --count[start];
        //继续游戏的条件为仍然有石头剩余
        while (count[0] != 0 || count[1] != 0 || count[2] != 0) {
            if (remainder == 2) {
                //余数为2，玩家必须取2或0
                if (count[2] == 0) {
                    if (count[0] == 0) {
                        //能继续游戏的石头（2）没得取了，但是石头还没取完，轮到Alice取的话就算Alice输，否则就是Alice赢
                        return !alice;
                    } else {
                        //没有2，取0
                        --count[0];
                    }
                } else {
                    //有2取2，余数为4%3=1
                    --count[2];
                    remainder = 1;
                }
            } else {
                //余数为1的情况，类似推理
                if (count[1] == 0) {
                    if (count[0] == 0) {
                        return !alice;
                    } else {
                        --count[0];
                    }
                } else {
                    --count[1];
                    remainder = 2;
                }
            }
            alice = !alice;
        }
        //石头取完了，Alice输了
        return false;
    }

    //p2038
    public boolean winnerOfGame(String colors) {
        char[] charArr = colors.toCharArray();
        //Alice删除和Bob删除互不影响，因此只要统计各自能删除的数量就可以直到谁胜利，Alice可删除的比Bob至少多1才能让Alice赢
        int i = 1, end = charArr.length - 1, aliceCount = 0, bobCount = 0;
        //true-Alice, false-Bob
        char lastColor = charArr[0], nextColor;
        while (i < end) {
            nextColor = charArr[i + 1];
            if (lastColor == charArr[i] && charArr[i] == nextColor) {
                if (charArr[i] == 'A') {
                    ++aliceCount;
                } else {
                    ++bobCount;
                }
            }
            lastColor = charArr[i];
            ++i;
        }
        return aliceCount - bobCount >= 1;
    }

    /**
     * 2216【贪心+栈思路】美化数组的最少删除数
     */
    public int minDeletion(int[] nums) {
        int answer = 0;
        Integer peek = null;
        for (int num : nums) {
            //一直找和栈顶不同的数，相同的数删掉就行
            if (null == peek) peek = num;
            else if (num == peek) ++answer;
            else peek = null;
        }
        if (null != peek) ++answer;
        return answer;
    }

    /**
     * 2578【贪心+优先队列】最小和分割
     */
    public int splitNum(int num) {
        PriorityQueue<Integer> mnPq = new PriorityQueue<>(Comparator.naturalOrder());
        while (num > 0) {
            int smaller = num / 10;
            int digit = num - (smaller * 10);
            mnPq.offer(digit);
            num = smaller;
        }
        int num1 = 0, num2 = 0;
        while (!mnPq.isEmpty()) {
            num1 *= 10;
            num1 += mnPq.poll();
            if (!mnPq.isEmpty()) {
                num2 *= 10;
                num2 += mnPq.poll();
            }
        }
        Integer.toString(num1);
        return num1 + num2;
    }

    /**
     * 3218【贪心+排序】切蛋糕的最小总开销 I
     */
    public int minimumCost(int m, int n, int[] horizontalCut, int[] verticalCut) {
        //每次出刀，贪心地考虑，应该先出开销最大的刀，因为每切一刀，后续的出刀次数都会在垂直维度增加1，开销小的刀放在最后切肯定更好
        Arrays.sort(horizontalCut);
        Arrays.sort(verticalCut);
        int answer = 0;
        int i = horizontalCut.length - 1, j = verticalCut.length - 1; //两个数组的下标
        int hc = 1, vc = 1; //每个维度出刀数量
        while (i >= 0 || j >= 0) {
            if (i >= 0 && j >= 0) {
                //两个维度都还有刀需要切，挑开销大的先切
                if (horizontalCut[i] >= verticalCut[j]) {
                    answer += horizontalCut[i] * hc; //出刀开销*对应维度需要出刀的数量
                    ++vc; //垂直维度出刀增加
                    --i;
                } else {
                    answer += verticalCut[j] * vc;
                    ++hc;
                    --j;
                }
            } else if (i >= 0) {
                answer += horizontalCut[i] * hc;
                --i;
            } else {
                answer += verticalCut[j] * vc;
                --j;
            }
        }
        return answer;
    }

    public static void main(String[] args) {
        GreedySolution solution = new GreedySolution();
        Assert.isTrue(67 == solution.minimumCost(5, 5, new int[]{1,2,3,4}, new int[]{6,5,4,3}));
//        Assert.isTrue(3 == solution.p1775MinOperations(new int[]{1,2,3,4,5,6}, new int[]{1,1,2,2,2,2}));
//        Assert.isTrue(-1 == solution.p1775MinOperations(new int[]{1,1,1,1,1,1,1}, new int[]{6}));
//        Assert.isTrue(3 == solution.p1775MinOperations(new int[]{6,6}, new int[]{1}));
//
//        Assert.isTrue(2 == solution.minElements(new int[]{1,-1,1}, 3, -4));
//        Assert.isTrue(1 == solution.minElements(new int[]{1,-10,9,1}, 100, 0));
//
//        Assert.isTrue("zzzzz".equals(solution.getSmallestString(5, 130)));
//
//        Assert.isTrue(2 == solution.minTaps(9, new int[]{0,5,0,3,3,3,1,4,0,4}));
//        Assert.isTrue(1 == solution.minTaps(8, new int[]{4,0,0,0,4,0,0,0,4}));
//        Assert.isTrue(3 == solution.minTaps(7, new int[]{1,2,1,0,2,1,0,1}));
//        Assert.isTrue(-1 == solution.minTaps(7, new int[]{1,2,1,0,2,1,0,0}));
//
//        Assert.isTrue(13 == solution.movesToMakeZigzag(new int[]{10,4,4,10,10,6,2,3}));
    }
}
